package com.lx.algorithm.LinkedList;

import com.primaryAlgorithm.RemoveNthFromEnd;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-09-21 00:38:01
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-09-21     张李鑫                     1.0         1.0 Version
 */
public class NodeTest1 {
    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    /**
     * 给定两个可能有环也可能无环的单链表，头节点head1和head2。
     * 请实现一个函数，如果两个链表相交，请返回相交的 第一个节点。如果不相交，返回null
     * 【要求】
     * 如果两个链表长度之和为N，时间复杂度请达到O(N)，额外空间复杂度 请达到O(1)。
     */
    public static ListNode getIntersectNode(ListNode head, ListNode head1) {
        //首先都走一遍 判断两个节点的情况
        ListNode loop = getLoop(head);
        ListNode loop1 = getLoop(head1);
        //都为空 说明不是循环链表
        if (null == loop && null == loop1) {
            int n = 0;
            ListNode p = head;
            ListNode p1 = head1;
            while (p.next != null) {
                n++;
                p = p.next;
            }
            while (p1.next != null) {
                n--;
                p1 = p1.next;
            }
            if (p1 != p) {
                return null;
            }
            ListNode more = n > 0 ? head : head1;
            ListNode less = n > 0 ? head1 : head;
            int abs = Math.abs(n);
            for (int i = 0; i < abs; i++) {
                more = more.next;
            }

            while (more != less) {
                more = more.next;
                less = less.next;
            }
            return less;
        } else if (loop != null && loop1 != null) {
            //如果相等的话说明他们在这个节点之前就相遇了
            //所以把进入环节点之后逻辑断链 找一个最大的先走n步然后一起遍历 相等的时候就是相遇返回
            if (loop == loop1) {
                ListNode p=head;
                ListNode p1=head1;
                int n=0;
                while (p.next!=loop){
                    p=p.next;
                    n++;
                }
                while (p1.next!=loop){
                    p1=p1.next;
                    n--;
                }
                ListNode more=n>0?head:head1;
                ListNode less=n>0?head1:head;
                int abs = Math.abs(n);
                for (int i = 0; i < abs; i++) {
                    more=more.next;
                }
                while (more!=less){
                    more=more.next;
                    less=less.next;
                }
                return more;

            } else {
                //先循环一圈找一下是否存在loop1 外圈判断是否回归到自己
                //如果找到随便找一个节点回复
                ListNode first = loop;
                while (first.next != loop) {
                    if (first.next == loop1) {
                        return loop;
                    }
                    first = first.next;
                }
                return null;
            }

        }
        //如果一个为空 一个不为空 说明两个必然不相交
        return null;
    }

    /**
     * <p>
     * 给一个节点获取
     * 如果当前节点是一个环节点
     * 返回环节点的入口
     * <p>
     * 结论:
     * 设置两个快慢指针
     * 指针1走一步 指针2走两步
     * 等指针2追上指针1 的时候 指针1回到头节点
     * 继续遍历然后相遇的节点就是入口节点
     * </p>
     *
     * @param node
     * @return com.lx.algorithm.LinkedList.NodeTest1.Node
     * @Author zlx
     * @date 2021/9/21
     */
    public static ListNode getLoop(ListNode node) {

        if (null == node || null == node.next || null == node.next.next) {
            return null;
        }
        ListNode first = node.next;
        ListNode next = node.next.next;

        while (first != next) {
            if (next.next == null || null == next.next.next) {
                return null;
            }
            first = first.next;
            next = next.next.next;
        }
        next = node;
        while (next != first) {
            next = next.next;
            first = first.next;
        }
        return next;
    }

}